This invention relates to a FIFO memory system and more particularly to a FIFO memory system for use in a serial digital communication system.
With digital communication systems having two or more processes running concurrently, transmission queues are used in order that the processes can efficiently transmit data to a communication line through a serial channel in the system. A common method of managing the transmission queues through the serial channel is to map each queue into one of a plurality of First-in-First-Out (FIFO) memories. The FIFOs are written to or filled by the system and emptied or read from by the communication process or vice versa.
A problem with this method is implementing a plurality of FIFOs in a limited area. The preferred solution is to utilise RAM based FIFO memories since they appear to require the least area.
The filling rate of the FIFO (i.e. the rate at which data is written to the FIFO) should normally be greater than the emptying rate of the FIFO (i.e. the rate at which data is read from the FIFO) onto the communication line. Typically, the FIFO issues Data Requests to the system any time a danger of underrun exists: underrun means carrying out a read operation from the FIFO when it is empty.
The latency of the system bus carrying the data to be written must be considered in order to determine the minimum size of each FIFO. The latency of the bus is defined as the maximum period of time required by the system to supply the first data to the FIFO after a Data Request has been generated. For limited size memory FIFOs, the maximum latency required is a critical parameter of the system configuration.
If Ls is the system latency having units of time, Ft is the rate at which the FIFO is emptied by the communication process and WM is the minimum FIFO size below which Data Requests are generated and assuming the FIFO is full when the first data is read by the communication process then, EQU WM=Ls*Ft (1)
With a FIFO having a size WM, once the FIFO is filled to its full size, the data requests will stop. However, Data Requests will be asserted again once the first data read is generated by the communication process in order to avoid an underrun state. Data Requests will therefore be issued all the time.
In order to avoid this situation, a FIFO having a size WM+Delta must be implemented. When a Data Request is sensed by the system, the system will fill the FIFO to its maximum size (WM+Delta). However, the Data Request will be asserted again only after the FIFO is emptied below the WM level.
A queuing system may comprise n different FIFOs for n different queues so that the total memory size MS must be greater than: EQU MS=(WM1+Delta1)+(WM2+Delta2)+. . .+(WMn+Deltan) (2)
Assuming the FIFOs are n similar FIFOs and Delta=WM, equation 2 becomes EQU MS=(2)(n) (WM)
Therefore, ##EQU1## From equation (1), EQU Ls*Ft=(MS)/(2n) (4)
And, EQU Ls=(MS)/(2n)*Ft (5)
Where Ls is the maximum latency acceptable to the memory system.
Thus, in order to account for the latency of the system bus and to avoid continuous Data Requests being generated, the above solution requires additional FIFO memory: that is, WM+Delta for each FIFO. The serial communication process can access only one FIFO at a time and this one FIFO should fill up to the size WM+Delta. Since the other FIFOs also occupy WM+Delta of memory when they only require WM of memory, with the above solution there is [(n-1)*Delta of unused bytes] of memory. Thus, large areas of memory are required but only a portion of the memory will be used at any one time.